package com.sicheng.蓝桥.练习题.dp.二维费用的背包问题;

import java.util.Scanner;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/5/9 22:48
 */
public class 宠物小精灵之收服 {
    /**
     * 傻东西 和 皮神 一起去抓 宝可梦
     * <p>
     * 一共会遇到 n 个 野生宝可梦，小智有 m 个 精灵球，皮神有 t 滴 血
     * <p>
     * 对于每个 野生宝可梦 来说，如果要捕捉他，需要 v1i 个 精灵球，战斗后皮神要掉 v2i 滴 血
     * <p>
     * 如果皮神 血量 ≤0，则小智停止狩猎
     * <p>
     * 小智对于每个 野生宝可梦 要么收服，要么逃跑
     * <p>
     * 求一种方案：收服 尽可能多 的 野生宝可梦 ；如果收服数量一样，要皮神 血量最多
     * <p>
     * 输出该方案的 野生宝可梦 收服数量，以及皮神战斗结束后的 剩余血量
     *
     * @param args
     */
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int t = scanner.nextInt();
        // dp[i][j]  是有i个球，j滴血的捕捉最大数量
        int[][] dp = new int[m + 1][t + 1];
        int[][] spend = new int[n][2];
        for (int i = 0; i < n; i++) {
            spend[i][0] = scanner.nextInt();
            spend[i][1] = scanner.nextInt();
        }

        for (int i = 0; i < n; i++) {
            for (int j = m; j >= spend[i][0]; j--) {
                //最后要剩一滴血,血量为0时无法捕捉
                //就是t滴血不能用完，dp的含义是可以用完的,所以从t-1开始
                for (int k = t - 1; k >= spend[i][1]; k--) {
                    dp[j][k] = Math.max(dp[j][k], dp[j - spend[i][0]][k - spend[i][1]] + 1);
                }
            }
        }

        System.out.println(dp[m][t - 1]);
        int cost = t;
        //找到最少血量时抓到最多精灵的血量
        for (int i = 0; i < t; i++) {
            if (dp[m][i] == dp[m][t - 1]) {
                cost = Math.min(cost, i);
            }
        }
        //剩余血量
        System.out.println(t - cost);

    }
}
